//
//  TwoFind.swift
//  PlayData
//
//  Created by 魏延龙 on 2022/5/9.
//

import Foundation

class TwoFind {
    
    /// 69. x 的平方根
    func mySqrt(_ x: Int) -> Int {
        var left = 0
        var right = x
        var ans = 0
        while left <= right {
            let mid = left + (right - left)/2
            if mid * mid < x {
                left = mid + 1
                ans = mid
            } else {
                right = mid - 1
            }
            
        }
        return ans
    }
    
//    /// 35. 搜索插入位置
//    func searchInsert(_ nums: [Int], _ target: Int) -> Int {
//        var left = 0
//        var right = nums.count - 1
//        var ans = 0
//        while left <= right {
//            let mid = left + (right - left)/2
//            if nums[mid] < target {
//                left = mid + 1
//                ans = mid
//            } else if nums[mid] > target {
//                right = mid - 1
//            } else {
//                ans = mid
//            }
//        }
//        return ans
//
//    }
    
    
    
    
    
    
    
    
    
    
    
    
    
    /// 二分查找 专项突破
    /// https://leetcode.cn/problems/binary-search/
    func search(_ nums: [Int], _ target: Int) -> Int {
        var left = -1
        var right = nums.count
        while left != right - 1 {
            let mid = (left + right) / 2
            if nums[mid] < target {
                left = mid
            } else if nums[mid] > target {
                right = mid
            } else {
                return mid
            }
        }
        return -1
    }
    
    /// https://leetcode.cn/problems/guess-number-higher-or-lower/
    func guessNumber(_ n: Int) -> Int {
        var left = 0
        var right = n + 1
        while left != right - 1 {
            let mid = (left + right) / 2
            if guess(mid) == -1 {
                right = mid
            } else if guess(mid) == 1 {
                left = mid
            } else {
                return mid
            }
        }
        return right
    }
    func guess(_ num: Int) -> Int {
        return 0
    }
    
    
    // MARK: 34. 在排序数组中查找元素的第一个和最后一个位置
    /*
     给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。
     如果数组中不存在目标值 target，返回 [-1, -1]。
     链接：https://leetcode.cn/problems/find-first-and-last-position-of-element-in-sorted-array
     */
    func searchRange(_ nums: [Int], _ target: Int) -> [Int] {
        var left = -1
        var right = nums.count
        
        var leftRes = -1
        var rightRes = -1
        
        // nums = [5,7,7,8,8,10], target = 8
        while left != right - 1 {
            let mid = (left + right) / 2
            if nums[mid] < target {
                left = mid
            } else {
                right = mid
            }
        }
        
        if (right != nums.count && nums[right] == target) {
            leftRes = right
        } else {
            return [leftRes, rightRes]
        }
        
        left = -1
        right = nums.count
        
        while left != right - 1 {
            let mid = (left + right) / 2
            if nums[mid] <= target {
                left = mid
            } else {
                right = mid
            }
        }
        
        if (left != -1 && nums[left] == target) {
            rightRes = left
        } else {
            return [leftRes, rightRes]
        }
        return [leftRes, rightRes]
    }
    
    // MARK: 35. 搜索插入位置
    /*
     给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
     https://leetcode.cn/problems/search-insert-position/
     */
    func searchInsert(_ nums: [Int], _ target: Int) -> Int {
        var left = -1
        var right = nums.count
        while left != right - 1 {
            let mid = (left + right) / 2
            if nums[mid] < target {
                left = mid
            } else {
                right = mid
            }
        }
        return right
    }
    
    // MARK: 852. 山脉数组的峰顶索引
    /*
     https://leetcode.cn/problems/peak-index-in-a-mountain-array/
     */
    func peakIndexInMountainArray(_ arr: [Int]) -> Int {
        var left = 0;
        var right = arr.count - 1;
        while left != right - 1 {
            let mid = (left + right) / 2
            if arr[mid] > arr[mid - 1] && arr[mid] > arr[mid + 1]{
                return mid
            } else if arr[mid] > arr[mid - 1] {
                left = mid
            } else {
                right = mid
            }
        }
        return right
    }
    
    
}

